package com.cqs.leetcode;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * Author:li
 * <p>
 * create date: 18-6-2 07:10
 */
public class PermutationsII47 {

    private List<List<Integer>> result = new ArrayList<>();
    private int[] nums;
    private int len;
    boolean[] visited;

    //8ms
    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        this.len = nums.length;
        visited = new boolean[this.len];
        List<Integer> list = new LinkedList<>();
        //需要先排序
        Arrays.sort(nums);
        next(list);
        return result;
    }

    private void next(List<Integer> list) {
        if (list.size() == len) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < len; i++) {
            //visited[i]同一索引的元素使用多次
            //i >= 1 && !visited[i - 1] && nums[i - 1] == nums[i]  表示nums在有序的情况下 在同一层 相同的元素只是排列一次

            if (visited[i] || (i >= 1 && !visited[i - 1] && nums[i - 1] == nums[i])) continue;
            visited[i] = true;
            list.add(nums[i]);
            next(list);
            //list.remove(new Integer(nums[i])); 删除的是第一个值为nums[i]元素
            //其实应该删除最后一个值为nums[i]元素
            list.remove(list.lastIndexOf(nums[i]));
            visited[i] = false;
        }
    }


    public static void main(String[] args) {
        PermutationsII47 permutations = new PermutationsII47();
        int[] nums = {2, 2, 1, 1};
        System.out.println(permutations.permuteUnique(nums));

        //
        System.out.println("----------------------");
        ArrayList<Integer> list = Lists.newArrayList(1, 2, 1, 2);
        list.remove(new Integer(2));
        System.out.println(list);
    }


    //14ms
    private static class Solution {
        private List<List<Integer>> result = new ArrayList<>();
        private int[] nums;
        private int len;
        boolean[] visited;

        public List<List<Integer>> permuteUnique(int[] nums) {
            this.nums = nums;
            this.len = nums.length;
            visited = new boolean[this.len];
            List<Integer> list = new LinkedList<>();
            next(list);
            return result;
        }

        private void next(List<Integer> list) {
            if (list.size() == len) {
                result.add(new ArrayList<>(list));
                return;
            }
            //借助set去重 (减去不必要的分支)
            Set<Integer> set = new HashSet<>(this.len);
            for (int i = 0; i < len; i++) {
                if (visited[i] || set.contains(nums[i])) continue;
                set.add(nums[i]);
                visited[i] = true;
                list.add(nums[i]);
                next(list);
                list.remove(list.lastIndexOf(nums[i]));
                visited[i] = false;
            }
        }
        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {2, 2, 1, 1};
            System.out.println(solution.permuteUnique(nums));

            //
            System.out.println("----------------------");
            ArrayList<Integer> list = Lists.newArrayList(1, 2, 1, 2);
            list.remove(new Integer(2));
            System.out.println(list);
        }
    }
}
